/* MutableTaskList.cpp
Copyright (c) 2008 Michael Zahniser
Please note the license terms (MIT license) at the end of this document.

Function definitions for the MutableTaskList class.
*/

#include "MutableTaskList.h"

#include <algorithm>
#include <sstream>

using std::stable_sort;
using std::for_each;
using std::ostringstream;



// operator[]:
// Get the task in the given row.
Task &MutableTaskList::operator[](int row)
{
	if((row < 0) | (row >= Rows()))
		return *begin();
	
	return *(rows[row + 1].it);
}



// Load:
// Load a task list from the given input stream.
// It stops reading when the end of the stream or the beginning of a new task list is found.
bool MutableTaskList::Load(istream &in)
{
	// Reset the selection and the list contents.
	selection.SetAnchorAndOffset(-1, 0);
	clear();
	
	Task::READ_LEGACY = !(in.peek());
	// Construct a task in the list, into which we will read the data.
	// This avoids having to make a copy of a fully initialized task.
	push_back(Task());
	
	bool dataWasLoaded = false;
	while(in >> back())
	{
		dataWasLoaded = true;
		push_back(Task());
		// Stop if the next entry is a task with depth 0 (the root of a new tree).
		if(Task::READ_LEGACY ? !in.peek() : (in.peek() > ' '))
			break;
	}
	
	// The last task in the list is empty. Get rid of it, unless it is the only task.
	if(size() > 1)
		pop_back();
	
	// Make sure the "is expandable" flags are correct.
	iterator next = begin();
	iterator previous = next;
	for(++next; next != end(); ++next)
	{
		if(next->Depth() > previous->Depth())
		{
			previous->SetExpandable(true);
			previous->Expand(next->IsRevealed());
		}
		previous = next;
	}

	// Update the record of visible rows.
	Update(begin(), begin());

	return dataWasLoaded;
}



// Save:
// Write this task list to the given output stream.
bool MutableTaskList::Save(ostream &out) const
{
	for(const_iterator it = begin(); it != end(); ++it)
		out<<*it;

	return true;
}



// Paste:
// Paste the given text after the end of the current row selection.
void MutableTaskList::Paste(const string &text, bool asChild)
{
	// Do nothing if there is no text to paste.
	if(text.empty())
		return;

	// If the selected row is the first row, the insertion must be as a child.
	asChild |= (selection == -1);

	// All depths will be relative to this one.
	// The pasted tree will be sorted so that its first member is at this depth.
	int baseDepth = RowIt(selection)->Depth() + asChild;
	int depthOffset = baseDepth;

	string::const_iterator it = text.begin();
	string::const_iterator last = text.end();

	iterator selectPoint = RowIt(selection.Last());
	iterator insertPoint = TreeEnd(selectPoint);
	if(asChild)
	{
		// If we are pasting text as a child of the selected task, make sure the
		// selected task is expanded.
		selectPoint->SetExpandable(true);
		selectPoint->Expand(false);
		ExpandBlock<true, false>(selectPoint, insertPoint);
	}
	selectPoint = --iterator(insertPoint);

	// Offset the base depth to match the indentation of the pasted items.
	// Skip whatever flags are at the start of the first line of text.
	if(*it == ':')
	{
		for(++it; it != last && *it != ':'; ++it) {}
		if(it == last)
			return;
		++it;
	}

	// Count the number of tabs before the first line of text.
	for( ; it != last && *it == '\t'; ++it)
		--depthOffset;
	it = text.begin();

	int previousDepth = baseDepth;

	// Parse the text into tasks.
	while(it != last)
	{
		Task task;
		task.Reveal();

		// Set the task flags.
		if(*it == ':')
		{
			string::const_iterator flagBegin = it;
			for(++it; it != last && *it != ':'; ++it) {}

			task.SetFlagString(string(flagBegin, ++it));
		}

		// Determine the depth of the task.
		int depth = depthOffset;
		for( ; it != last && *it == '\t'; ++it)
			++depth;

		// Bail out if there is no text after the tabs or if the number of tabs
		// results in an indentation less than the base amount.
		if((it == last) | (depth < baseDepth))
			break;

		// Set the depth of the task. If it is a child of the previous task, make
		// sure that previous task is expanded. (It should be automatically if the
		// flag string was correct).
		task.SetDepth(depth);
		if(depth > previousDepth)
		{
			iterator parent = insertPoint;
			--parent;
			parent->SetExpandable(true);
			parent->Expand(true);
		}
		previousDepth = depth;

		// Locate the end of the line.
		string::const_iterator lineBegin = it;

		for( ; it != last && *it != '\n'; ++it) {}

		string::const_iterator lineEnd = it;
		if(it != last)
			++it;
		if(lineEnd != last && *(lineEnd - 1) == '\r')
			--lineEnd;

		// Find the date string, if any.
		string::const_iterator dateEnd = lineEnd;
		if(*--dateEnd == ')')
		{
			string::const_iterator dateIt = dateEnd;
			for(--dateIt; dateIt > lineBegin && *dateIt != '('; --dateIt) {}

			if(*dateIt == '(')
			{
				task.SetDate(string(dateIt + 1, dateEnd));
				if(task.HasDate())
					lineEnd = dateIt - 1;
			}
		}

		// Set the text of the task.
		task.SetText(string(lineBegin, lineEnd));

		// Insert this new task into the list.
		// TODO: Add a constructor to Task that does all this automatically, creating a Task
		// based on an input stream.
		insert(insertPoint, task);
	}

	// Update the record of what is visible.
	Update(++selectPoint, insertPoint);
}



// Copy:
// Convert the selected rows to a string.
// A cut is equivalent to a Copy() followed by a DeleteSelection().
const string &MutableTaskList::Copy(bool withFlags) const
{
	// For efficiency, always use the same string to store the result.
	// This function will never be called by more than one thread, so this is safe.
	static string text;
	text.clear();

	// Figure out what rows are selected.
	const_iterator first = RowIt(selection.First());
	const_iterator last = end();
	if(selection.Last() < Rows() - 1)
		last = RowIt(selection.Last() + 1);

	// Convert each task into a string.
	for(const_iterator it = first; it != last; ++it)
	{
		if(withFlags)
			text += it->GetFlagString();
		text += string(it->Depth(), '\t');
		text += it->Text();
		if(it->HasDate())
			text += " (" + it->Date() + ")";
		// For compatibility with Windows, use Windows-style newlines. All other systems
		// can automatically handle different newline forms.
		text += "\r\n";
	}

	return text;
}



// Expand:
// Expand the selected rows.
void MutableTaskList::Expand()
{
	if(selection == -1)
		selection.SetFirstAndLast(0, Rows() - 1);
	ForEachTree<&MutableTaskList::ExpandBlock<true, false> >();
}



// Collapse:
// Collapse the selected rows.
void MutableTaskList::Collapse()
{
	if(selection == -1)
		selection.SetFirstAndLast(0, Rows() - 1);
	ForEachTree<&MutableTaskList::ExpandBlock<false, false> >();
}



// RecursiveExpand:
// Expand the selected rows and all their children.
void MutableTaskList::RecursiveExpand()
{
	if(selection == -1)
		selection.SetFirstAndLast(0, Rows() - 1);
	ForEachTree<&MutableTaskList::ExpandBlock<true, true> >();
}



// RecursiveCollapse:
// Collapse the selected rows and all their children.
void MutableTaskList::RecursiveCollapse()
{
	if(selection == -1)
		selection.SetFirstAndLast(0, Rows() - 1);
	ForEachTree<&MutableTaskList::ExpandBlock<false, true> >();
}



// Toggle:
// Toggle the given flag for all the selected rows.
void MutableTaskList::Toggle(unsigned short flag)
{
	// If the root node is selected, apply the operation to all tasks.
	iterator first = begin();
	iterator last = end();

	// Otherwise, apply the operation to the selected rows.
	if(selection != -1)
	{
		first = RowIt(selection.First());
		last = ++RowIt(selection.Last());
	}

	// All flags will be set to the opposite of what the first selected task is set to.
	bool set = !first->GetFlag(flag);

	for_each(first, last, SetFlagOfVisibles(flag, set));
}



// RecursiveToggle:
// Toggle the given flag for all the selected rows and their children.
void MutableTaskList::RecursiveToggle(unsigned short flag)
{
	// If the root node is selected, apply the operation to all tasks.
	iterator first = begin();
	iterator last = end();

	// Otherwise, apply the operation to the selected rows. Make sure the range we
	// are using contains all children of the selected nodes, as well.
	if(selection != -1)
	{
		first = RowIt(selection.First());
		last = ++RowIt(selection.Last());

		iterator it = first;
		iterator lowest = it;

		for( ; it != last; ++it)
			if(it->Depth() <= lowest->Depth())
				lowest = it;
		last = TreeEnd(lowest);
	}
	
	// All flags will be set to the opposite of what the first selected task is set to.
	bool set = !first->GetFlag(flag);

	for_each(first, last, SetFlagOfAll(flag, set));
}



// InsertSibling:
// Insert a new task after the last selected task, and select it.
void MutableTaskList::InsertSibling()
{
	// If the root is selected, insert a task as the child of the root.
	if(selection == -1)
	{
		InsertChild();
		return;
	}
	
	// Find the end of whatever tree depends from the last selected task.
	iterator parent = RowIt(selection.Last());
	iterator after = TreeEnd(parent);

	// Insert a task there.
	iterator inserted = insert(after, Task());
	inserted->SetDepth(parent->Depth());
	inserted->Reveal();

	// Update the rows and the selection.
	Update(inserted, after);
}



// InsertChild:
// Insert a new task as the child of the last selected task.
void MutableTaskList::InsertChild()
{
	// Insert immediately after the last task.
	iterator parent = RowIt(selection.Last());
	iterator after = ++iterator(parent);

	// Make sure the last task is expanded.
	parent->SetExpandable(true);
	parent->Expand(false);

	// Insert the task.
	iterator inserted = insert(after, Task());
	inserted->SetDepth(parent->Depth() + 1);

	// Expand the entire tree depending from the parent task.
	ExpandBlock<true, false>(parent, TreeEnd(parent));

	// Update the display rows and the selection.
	Update(inserted, after);
}



// MoveUp:
// Move the selected tasks up.
void MutableTaskList::MoveUp()
{
	ForEachTree<&MutableTaskList::MoveBlockUp>();
}



// MoveDown:
// Move the selected tasks down.
void MutableTaskList::MoveDown()
{
	ForEachTree<&MutableTaskList::MoveBlockDown>();
}



// MoveIn:
// Indent the selected tasks, if possible.
// This is not possible if the first task is already indented relative to the
// task above it.
void MutableTaskList::MoveIn()
{
	ForEachTree<&MutableTaskList::MoveBlockIn>();
}



// MoveOut:
// Outdent the selected tasks, if possible.
// This is not possible if one of the tasks has depth 1.
void MutableTaskList::MoveOut()
{
	ForEachTree<&MutableTaskList::MoveBlockOut>();
}



// DeleteSelection:
// Delete the selected tasks.
void MutableTaskList::DeleteSelection()
{
	ForEachTree<&MutableTaskList::DeleteBlock>();
}



// SortAlphabetical:
// Sort the siblings of the node in the given row.
// If the root row is given, sort its children instead.
void MutableTaskList::SortAlphabetical(bool reverse)
{
	Sort(LessAlphabetical(reverse));
}



// SortByDate:
// Sort the siblings of the node in the given row.
// If the root row is given, sort its children instead.
void MutableTaskList::SortByDate(bool reverse)
{
	Sort(LessByDate(reverse));
}


	
// Swap in a new list for this category.
void MutableTaskList::SwapList(list<Task> &newList)
{
	newList.swap(*this);
	
	Update(begin(), end());
}



template <MutableTaskList::MemFun fun>
void MutableTaskList::ForEachTree()
{
	// Break the current selection up into individual trees such that no tree is
	// contained in another.
	TreeList &siblings = FindTrees();
	iterator first = siblings.front().first;
	iterator last = siblings.back().second;
	
	// If we're deleting the selection, we need to modify the selection
	// differently than normal because the selected lines will cease to exist.
	bool isEntireFamily = false;
	if(fun == &MutableTaskList::DeleteBlock)
	{
		int depth = first->Depth();
		--first;
		iterator afterLast = ++iterator(last);

		// If all the children of a task are deleted, that task is no longer expandable.
		isEntireFamily = (first->Depth() < depth) && ((afterLast == end()) || (afterLast->Depth() < depth));
	}
	
	// Begin applying the procedure either to the last tree or to the first one depending on the procedure.
	if((fun == &MutableTaskList::MoveBlockDown) || (fun == &MutableTaskList::MoveBlockOut))
	{
		for(TreeList::reverse_iterator it = siblings.rbegin(); it != siblings.rend(); ++it)
			if(!(this->*fun)(it->first, ++iterator(it->second)))
				break;
	}
	else
	{
		for(TreeList::iterator it = siblings.begin(); it != siblings.end(); ++it)
			if(!(this->*fun)(it->first, ++iterator(it->second)))
				break;
	}

	// If deleting, move the selection to the line below the deleted lines,
	// unless the deleted lines were at the end of the list.
	if(fun == &MutableTaskList::DeleteBlock)
	{
		if(isEntireFamily)
		{
			// If all the children of a task are deleted, that task is no longer expandable.
			first->SetExpandable(false);
			first->Expand(false);
		}

		++first;
		if(first == end())
			--first;
		last = first;
	}
	
	// Update the display rows and the selection.
	Update(first, ++last);
}



// MoveBlockUp:
// Move the given block of tasks up.
bool MutableTaskList::MoveBlockUp(iterator first, iterator last)
{
	iterator insertPoint = PreviousSibling(first);
	
	// The selected tasks cannot be moved up if the top task is already the first child of its parent.
	bool canMove = (insertPoint != first);
	
	if(canMove)
		splice(insertPoint, *this, first, last);
		
	return canMove;
}



// MoveBlockDown:
// Move the given block of tasks down.
bool MutableTaskList::MoveBlockDown(iterator first, iterator last)
{
	iterator insertPoint = TreeEnd(last);
	
	// The selected tasks cannot be moved down unless another child of their common parent
	// exists after them.
	bool canMove = (last->Depth() == first->Depth());
	
	if(canMove)
		splice(insertPoint, *this, first, last);
		
	return canMove;
}



// MoveBlockIn:
// Indent the given block of tasks.
bool MutableTaskList::MoveBlockIn(iterator first, iterator last)
{
	// We can only indent this tree if it has a previous sibling to become part of.
	// That will be true if the line above this one has equal or greater depth.
	iterator previous = PreviousSibling(first);
	if(previous == first)
		return false;

	previous->SetExpandable(true);
	// Mark the previous node as unexpanded, so that Expand() will work on it.
	previous->Expand(false);

	// Expand the new parent, if it is not already expanded.
	ExpandBlock<true, false>(previous, first);

	// Indent this tree.
	for_each(first, last, ChangeDepth<1>());
	
	return true;
}



// MoveBlockOut:
// Outdent the given block of tasks.
bool MutableTaskList::MoveBlockOut(iterator first, iterator last)
{
	if(first->Depth() < 2)
		return false;
		
	// Find the end of the tree's parent, beginning here.
	iterator insertPoint = last;
	for( ; insertPoint != end() && insertPoint->Depth() >= first->Depth(); ++insertPoint) {}

	// Outdent this tree.
	for_each(first, last, ChangeDepth<-1>());

	// Move the tree to the end of the parent.
	splice(insertPoint, *this, first, last);

	// If this was the last child of the parent, mark it as not expandable or expanded.
	iterator previous = --iterator(first);
	if(previous->Depth() == first->Depth())
	{
		previous->SetExpandable(false);
		previous->Expand(false);
	}
	
	return true;
}



// ExpandBlock:
// Expand or collapse a node, and optionally all its descendents as well.
template <bool reveal, bool recursive>
bool MutableTaskList::ExpandBlock(iterator first, iterator last)
{
	// Do nothing if this node is not expandable.
	if(!first->IsExpandable() | (first->IsExpanded() == reveal))
		return true;

	first->Expand(reveal);

	// Iterate through all tasks in the rangle, revealing / hiding them.
	for(++first; first != last; ++first)
	{
		first->Reveal(reveal);

		if(first->IsExpandable())
		{
			// If we're doing a recursive expand, the final expanded state of _all_
			// tasks in the range should be set.
			// Otherwise, skip processing any tasks that are children of an unexpanded node.
			if(recursive)
				first->Expand(reveal);
			else if(!first->IsExpanded())
				first = --TreeEnd(first);
		}
	}
	
	return true;
}



// DeleteBlock:
// Erase all the tasks in the given range.
bool MutableTaskList::DeleteBlock(iterator first, iterator last)
{
	erase(first, last);
	
	return true;
}



// Sort:
// This must be private, because it is defined in the .cpp file where no
// derived class will be able to access it.
template <class Compare>
void MutableTaskList::Sort(Compare compare)
{
	// Get a list of all siblings of the selected task.
	TreeList &siblings = FindSiblings();
	if(siblings.empty())
		return;
	
	iterator insertionPoint = ++iterator(siblings.back().second);

	// Sort those siblings, then rearrange them in the tree.
	stable_sort(siblings.begin(), siblings.end(), compare);
	
	for(TreeList::const_iterator it = siblings.begin(); it != siblings.end(); ++it)
		splice(insertionPoint, *this, it->first, ++iterator(it->second));
	
	Update(siblings.front().first, insertionPoint);
}



// Parent:
// Get the parent of the given task. That is, the first task above it
// with a depth less than it.
MutableTaskList::iterator MutableTaskList::Parent(iterator it)
{
	int depth = it->Depth();
	if(depth)
		for(--it; it->Depth() >= depth; --it) {}

	return it;
}



// PreviousSibling:
// Get the previous sibline of the given task, if any.
// That is, the first task above the given task that has a depth less than or
// equal to the given task. If the depth is less, it is not a sibling, but a parent.
MutableTaskList::iterator MutableTaskList::PreviousSibling(iterator it)
{
	if(it == begin())
		return begin();

	iterator sibling = it;
	for(--sibling; sibling->Depth() > it->Depth(); --sibling) {}

	// Check for tasks that are the first child of their parent.
	if(sibling->Depth() < it->Depth())
		return it;
	return sibling;
}



// NextSibling:
// Get the next sibling of the given task.
// That is, the first task below the given task with a depth less than or
// equal to the given task. If the depth is less, there is no next sibling.
MutableTaskList::iterator MutableTaskList::NextSibling(iterator it)
{
	if(it == begin())
		return end();

	iterator sibling = TreeEnd(it);

	// Check for tasks that are the last child of their parent.
	if(sibling->Depth() < it->Depth())
		return it;
	return sibling;
}



// TreeEnd:
// Get an iterator to the first task below the given task that is not in its subtree.
MutableTaskList::iterator MutableTaskList::TreeEnd(iterator it)
{
	if(it == begin())
		return end();

	iterator sibling = it;
	for(++sibling; sibling != end() && sibling->Depth() > it->Depth(); ++sibling) {}

	return sibling;
}



// RowIt:
// Convert a row of the display into an iterator to a task.
MutableTaskList::iterator MutableTaskList::RowIt(int row)
{
	return rows[row + 1].it;
}



// RowIt:
// Convert a row of the display into an iterator to a task.
MutableTaskList::const_iterator MutableTaskList::RowIt(int row) const
{
	return rows[row + 1].it;
}



// FindSiblings:
// Iterate through all siblings of the selected row, recording the start and end
// of each sibling's subtree. This is for performing a sort on all tasks that are
// siblings of the selected task.
MutableTaskList::TreeList &MutableTaskList::FindSiblings()
{
	static TreeList siblings;
	siblings.clear();
	
	pair<iterator, iterator> family;
	family.first = Parent(RowIt(selection));
	
	// We will iterate until we pass out of this subtree.
	int rootDepth = family.first->Depth();
	
	while(++family.first != end())
	{
		if(family.first->Depth() <= rootDepth)
			break;
		
		// Find the end of this sibling's tree, and store it in the siblings vector.
		family.second = --TreeEnd(family.first);
		siblings.push_back(family);
		// The start of each new tree is the end of the previous one.
		family.first = family.second;
	}
	
	return siblings;
}



// FindTrees:
// Iterate through all selected rows, breaking them up into blocks of tasks where
// each task in a block is a child of the first task in the block. This is to allow
// operations to be performed on disjoint trees.
MutableTaskList::TreeList &MutableTaskList::FindTrees()
{
	static TreeList siblings;
	siblings.clear();
	
	// If the root node is selected, apply the operation to all of its children.
	iterator first = begin();
	iterator last = end();

	// Otherwise, only process the selected rows.
	if(selection != -1)
	{
		first = RowIt(selection.First());
		last = ++RowIt(selection.Last());
	}

	bool done = false;
	while(!done)
	{
		// Find the end of first's subtree.
		iterator it = first;
		for(++it; it != end() && it->Depth() > first->Depth(); ++it)
			done |= (it == last);
		done |= (it == last);
		
		// Store the tree we just found, then start searching at the end of that tree.
		siblings.push_back(pair<iterator, iterator>(first, --iterator(it)));
		first = it;
	}
	
	return siblings;
}



/* Copyright (c) 2008 Michael Zahniser

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE. */
